package com.zhang.map;

import com.zhang.printer.BinaryTreeInfo;
import com.zhang.printer.BinaryTrees;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * @author 张吉鑫
 * @Description 用数组和红黑树 实现HashMap
 * @date 2021/3/25 15:19
 */
public class HashMap<K, V> implements Map<K, V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private int size;
    private Node<K, V>[] table;
    private static final int DEFAULT_CAPACITY = 1 << 4;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashMap() {
        table = new Node[DEFAULT_CAPACITY];
    }

    /**
     * 获取元素数量
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 循环遍历清空数组所有元素
     */
    @Override
    public void clear() {
        if (size == 0) {
            return;
        }
        for (int i = 0; i < table.length; i++) {
            table[i] = null;
        }
        size = 0;
    }

    /**
     * 添加键值对
     * 
     * @param k1
     * @param value
     * @return
     */
    @Override
    public V put(K k1, V value) {
        resize();
        int index = index(k1);
        Node<K, V> root = table[index];

        if (root == null) {
            root = createNode(k1, value, null);
            size++;
            fixAfterPut(root);
            table[index] = root;
            return null;
        }

        Node<K, V> node = root;
        Node<K, V> parent;
        int cmp;
        int h1 = hash(k1);
        Node<K, V> result;
        boolean searched = false;
        do {
            int h2 = node.hash;
            K k2 = node.key;
            if (h1 > h2) {
                cmp = 1;
            } else if (h1 < h2) {
                cmp = -1;
            } else if (Objects.equals(k1, k2)) {
                cmp = 0;
            } else if (k1 != null && k2 != null &&
                    k1 instanceof Comparable &&
                    k1.getClass() == k2.getClass() &&
                    (cmp = ((Comparable) k1).compareTo(k2)) != 0){
            }else if (searched){
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }else if ((node.left != null && (result = node(node.left, k1)) != null) || (node.right != null && (result = node(node.right, k1)) != null)) {
                node = result;
                cmp = 0;
            }else {
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
                searched = true;
            }

            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                V value1 = node.value;
                node.key = k1;
                node.value = value;
                return value1;
            }
        } while (node != null);

        Node<K, V> newNode = createNode(k1, value, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        size++;
        fixAfterPut(newNode);
        return null;

    }

    @Override
    public V get(K key) {
        Node<K, V> node = node(key);
        return node == null ? null : node.value;
    }

    @Override
    public V remove(K key) {
        return remove(node(key));
    }

    @Override
    public boolean containsKey(K key) {
        return node(key) != null;
    }

    @Override
    public boolean containsValue(V value) {
        if (size == 0) {
            return false;
        }
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            if (node == null) {
                continue;
            }
            Queue<Node<K, V>> queue = new LinkedList<>();
            queue.offer(node);
            while (!queue.isEmpty()) {
                Node<K, V> poll = queue.poll();

                if (poll.value == value) {
                    return true;
                }

                if (poll.left != null) {
                    queue.offer(poll.left);
                }

                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
        return false;
    }

    @Override
    public void traversal(Visitor visitor) {
        if (size == 0 || visitor == null) {
            return;
        }
        Queue<Node<K, V>> queue = new LinkedList<>();
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];
            if (node == null) {
                continue;
            }
            queue.offer(node);
            while (!queue.isEmpty()) {
                Node<K, V> poll = queue.poll();

                if (visitor.visit(poll.key, poll.value)) {
                    return;
                }

                if (poll.left != null) {
                    queue.offer(poll.left);
                }

                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
        }
    }

    /**
     * 调整数组大小
     */
    private void resize(){
        if (size / table.length <= DEFAULT_LOAD_FACTOR){
            return;
        }

        Node<K,V>[] oldTable = table;
        table = new Node[table.length << 1];

        Queue<Node<K,V>> queue = new LinkedList<>();

        for (int i = 0; i < oldTable.length; i++) {
            Node<K, V> node = oldTable[i];
            if (node == null){
                continue;
            }
            queue.offer(node);
            while (!queue.isEmpty()){
                Node<K, V> poll = queue.poll();

                if (poll.left != null){
                    queue.offer(poll.left);
                }
                if (poll.right != null){
                    queue.offer(poll.right);
                }

                moveNode(poll);
            }
        }
    }

    /**
     * 移动节点
     * @param newNode
     */
    private void moveNode(Node<K,V> newNode){
        newNode.parent = null;
        newNode.left = null;
        newNode.right = null;
        newNode.color = RED;

        int index = index(newNode);
        Node<K, V> root = table[index];

        if (root == null) {
            root = newNode;
            fixAfterPut(root);
            table[index] = root;
            return;
        }

        Node<K, V> node = root;
        Node<K, V> parent;
        int cmp;
        K k1 = newNode.key;
        int h1 = newNode.hash;
        do {
            int h2 = node.hash;
            K k2 = node.key;
            if (h1 > h2) {
                cmp = 1;
            } else if (h1 < h2) {
                cmp = -1;
            } else if (k1 != null && k2 != null &&
                    k1 instanceof Comparable &&
                    k1.getClass() == k2.getClass() &&
                    (cmp = ((Comparable) k1).compareTo(k2)) != 0){
            }else{
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }

            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            }
        } while (node != null);

        if (cmp > 0) {
            parent.right = newNode;
        } else if (cmp < 0) {
            parent.left = newNode;
        }
        newNode.parent = parent;
        fixAfterPut(newNode);
    }

    public void print() {
        for (int i = 0; i < table.length; i++) {
            Node<K, V> node = table[i];

            BinaryTreeInfo info = new BinaryTreeInfo() {
                @Override
                public Object root() {
                    return node;
                }

                @Override
                public Object left(Object node) {
                    return ((Node<K, V>) node).left;
                }

                @Override
                public Object right(Object node) {
                    return ((Node<K, V>) node).right;
                }

                @Override
                public Object string(Object node) {
                    return node;
                }
            };
            BinaryTrees.println(info);
        }
    }

    private V remove(Node<K, V> node) {
        if (node == null) {
            return null;
        }
        Node<K,V> willNode = node;
        V value = node.value;

        size--;

        if (node.hasTwoChildren()) {//度为2
            Node<K, V> p = predecessor(node);
            node.key = p.key;
            node.value = p.value;
            node.hash = p.hash;
            node = p;
        }

        Node<K, V> childNode = node.left != null ? node.left : node.right;

        int index = index(node);

        if (childNode != null) {//度为1
            childNode.parent = node.parent;
            if (childNode.parent == null) {//如果删除的节点父节点是null 说明是根节点
                table[index] = childNode;
            } else if (childNode.parent.left == node) {
                childNode.parent.left = childNode;
            } else {
                childNode.parent.right = childNode;
            }
            fixAfterRemove(node, childNode);
        } else if (node.parent == null) {//是叶子节点 又是根节点
            table[index] = null;
            fixAfterRemove(node, null);
        } else {//是叶子节点 度为0
            if (node.parent.left == node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            fixAfterRemove(node, null);
        }
        afterRemove(willNode,node);
        return value;
    }

    /**
     * 通过key查找节点
     *
     * @param key
     * @return
     */
    private Node<K, V> node(K key) {
        int index = index(key);
        Node<K, V> node = table[index];
        return node == null ? null : node(node, key);
    }

    private Node<K, V> node(Node<K, V> node, K k1) {
        int h1 = hash(k1);
        int cmp;
        Node<K, V> result;
        while (node != null) {
            int h2 = node.hash;
            K k2 = node.key;
            if (h1 > h2) {
                node = node.right;
            } else if (h1 < h2) {
                node = node.left;
            } else if (Objects.equals(k1, k2)) {
                return node;
            } else if (k1 != null && k2 != null && k1 instanceof Comparable && k1.getClass() == k2.getClass()  &&  (cmp = ((Comparable) k1).compareTo(k2)) != 0 ){
                node = cmp > 0 ? node.right : node.left;
            }else if (node.left != null && (result = node(node.left, k1)) != null) {
                return result;
            } else{
                node = node.right;
            }
        }
        return null;
    }

    /**
     * 添加后调整平衡
     *
     * @param node
     */
    private void fixAfterPut(Node<K, V> node) {
        Node<K, V> parent = node.parent;

        if (parent == null) {
            black(node);
            return;
        }

        /**
         * parent是黑色节点 不用做任何处理
         */
        if (isBlack(parent)) {
            return;
        }

        /**
         * 判断祖父节点是否是黑色
         */
        Node<K, V> grand = parent.parent;
        if (isBlack(parent.sibling())) {

            grand = red(grand);

            if (parent.isLeftChild()) {//L
                if (node.isLeftChild()) {//LL
                    parent = black(parent);
                } else {//LR
                    node = black(node);
                    rotateLeft(parent);
                }
                rotateRight(grand);
            } else {//R
                if (node.isLeftChild()) {//RL
                    node = black(node);
                    rotateRight(parent);
                } else {//RR
                    parent = black(parent);
                }
                rotateLeft(grand);
            }
        } else {//叔父节点是红色的
            parent = black(parent);
            black(parent.sibling());
            fixAfterPut(red(grand));
        }

    }

    /**
     * 删除后调整平衡
     *
     * @param node
     * @param childNode
     */
    private void fixAfterRemove(Node<K, V> node, Node<K, V> childNode) {
        //如果删除的节点是红色 直接删除
        if (isRed(node)) {
            return;
        }

        //如果替代的节点是红色的 把替代的节点染成黑色
        if (isRed(childNode)) {
            black(childNode);
            return;
        }

        Node<K, V> parent = node.parent;
        //如果父节点是空的 说明删除节点就是根节点
        if (parent == null) {
            return;
        }
        //获取删除节点的兄弟节点
        boolean left = parent.left == null || node.isLeftChild();
        Node<K, V> sibling = left ? parent.right : parent.left;


        //如果兄弟节点在父节点的左边
        if (sibling.isLeftChild()) {
            //如果兄弟节点是红色的
            if (isRed(sibling)) {
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;
            }
            //如果兄弟节点两个子节点都是黑色的
            if (isBlack(sibling.left) && isBlack(sibling.right)) {
                //如果父类是黑色节点 会产生下溢 再次调用方法 把父类节点当初删除节点处理
                boolean b = colorOf(parent);
                red(sibling);
                black(parent);
                if (b) {
                    fixAfterRemove(parent, null);
                }
            } else {
                //兄弟节点至少有一个红色节点
                boolean b = colorOf(parent);
                if (isRed(sibling.right)) {
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling, b);
                black(parent);
                black(sibling.left);
                rotateRight(parent);
            }
        } else {
            //如果兄弟节点是红色的
            if (isRed(sibling)) {
                black(sibling);
                red(parent);
                rotateLeft(parent);
                sibling = parent.right;
            }
            //如果兄弟节点两个子节点都是黑色的
            if (isBlack(sibling.right) && isBlack(sibling.left)) {
                //如果父类是黑色的 会产生下溢现象 把父类节点当作删除节点 重新调用方法
                boolean b = colorOf(parent);
                red(sibling);
                black(parent);
                if (b) {
                    fixAfterRemove(parent, null);
                }
            } else {
                //兄弟节点至少有一个红色节点
                boolean b = colorOf(parent);
                if (isRed(sibling.left)) {
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling, b);
                black(parent);
                black(sibling.right);
                rotateLeft(parent);
            }
        }
    }


    /**
     * 前驱节点
     *
     * @param node
     * @return
     */
    private Node<K, V> predecessor(Node<K, V> node) {

        if (node == null) {
            return null;
        }

        if (node.left != null) {
            Node<K, V> n = node.left;
            while (n.right != null) {
                n = n.right;
            }
            return n;
        }
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 后继节点
     *
     * @param node
     * @return
     */
    private Node<K, V> successor(Node<K, V> node) {
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            Node<K, V> s = node.right;
            while (s.left != null) {
                s = s.left;
            }
            return s;
        }
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }


    /**
     * 左旋转
     *
     * @param grand
     */
    private void rotateLeft(Node<K, V> grand) {
        Node<K, V> parent = grand.right;
        Node<K, V> child = parent.left;
        grand.right = child;
        parent.left = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 右旋转
     *
     * @param grand
     */
    private void rotateRight(Node<K, V> grand) {
        Node<K, V> parent = grand.left;
        Node<K, V> child = parent.right;
        grand.left = child;
        parent.right = grand;

        afterRotate(grand, parent, child);
    }

    /**
     * 旋转后 更新高度
     *
     * @param grand
     * @param parent
     * @param child
     */
    private void afterRotate(Node<K, V> grand, Node<K, V> parent, Node<K, V> child) {
        if (grand.parent == null) {
            table[index(grand)] = parent;
        } else if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else {
            grand.parent.right = parent;
        }
        parent.parent = grand.parent;
        grand.parent = parent;

        if (child != null) {
            child.parent = grand;
        }

    }

    /**
     * 染色的方法
     *
     * @param node
     * @param color
     * @return
     */
    private Node<K, V> color(Node<K, V> node, boolean color) {
        if (node == null) {
            return node;
        }
        node.color = color;
        return node;
    }

    /**
     * 染成红色
     *
     * @param node
     * @return
     */
    private Node<K, V> red(Node<K, V> node) {
        return color(node, RED);
    }

    /**
     * 染成黑色
     *
     * @param node
     * @return
     */
    private Node<K, V> black(Node<K, V> node) {
        return color(node, BLACK);
    }

    /**
     * 查看节点颜色
     *
     * @param node
     * @return
     */
    private boolean colorOf(Node<K, V> node) {
        return node == null ? BLACK : node.color;
    }

    /**
     * 判断节点是否为黑色
     *
     * @param node
     * @return
     */
    private boolean isBlack(Node<K, V> node) {
        return colorOf(node) == BLACK;
    }

    /**
     * 判断节点是否为红色
     *
     * @param node
     * @return
     */
    private boolean isRed(Node<K, V> node) {
        return colorOf(node) == RED;
    }

    /**
     * 比较器
     *
     * @param e1
     * @param e2
     * @return
     */
    private int compare(K e1, K e2, int hash1, int hash2) {
        int cmp = hash1 - hash2;
        //比较hash值
        if (cmp != 0) {
            return cmp;
        }

        //比较equals
        if (Objects.equals(e1, e2)) {
            return 0;
        }

        if (e1 != null && e2 != null) {
            String name = e1.getClass().getName();
            String name2 = e2.getClass().getName();
            int i = name.compareTo(name2);
            //比较类名
            if (i != 0) {
                return i;
            }
            //比较器
            if (e1 instanceof Comparable) {
                return ((Comparable) e1).compareTo(e2);
            }
        }
        //比较地址值
        return System.identityHashCode(e1) - System.identityHashCode(e2);
    }

    protected void afterRemove(Node<K,V> willNode,Node<K,V> removeNode){
    }

    /**
     * 创建一个新的节点
     *
     * @param key
     * @param value
     * @param parent
     * @return
     */
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        return new Node<>(key, value, parent);
    }

    /**
     * 通过哈希值计算索引
     * 用元素计算出的哈希值跟数组长度取余 计算出索引
     * hashCode & (table.length - 1) 代替 hashCode % table.length ;可以提升效率
     *
     * @param key
     * @return
     */
    private int index(K key) {
        return hash(key) & (table.length - 1);
    }

    private int index(Node<K, V> node) {
        return node.hash & (table.length - 1);
    }

    /**
     * 计算哈希值
     * 如果元素为空 直接返回0索引
     * 如果元素不为空 获取元素的哈希值 然后用二进制高16位 与 低16位再次计算
     * 最后返回结果
     *
     * @param key
     * @return
     */
    private int hash(K key) {
        if (key == null) {
            return 0;
        }
        int hashCode = key.hashCode();
        hashCode = hashCode ^ (hashCode >>> 16);
        return hashCode;
    }

    protected static class Node<K, V> {
        int hash;
        K key;
        V value;
        boolean color = RED;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent;

        public Node(K key, V value, Node<K, V> parent) {
            this.key = key;
            int hash = key == null ? 0 : key.hashCode();
            this.hash = hash ^ (hash >>> 16);
            this.value = value;
            this.parent = parent;
        }

        /**
         * 判断是否为叶子节点
         *
         * @return
         */
        public boolean isLeaf() {
            return left == null && right == null;
        }

        /**
         * 判断是否有两个子节点
         *
         * @return
         */
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }

        /**
         * 判断是否是父节点的左子节点
         *
         * @return
         */
        public boolean isLeftChild() {
            return parent != null && this == parent.left;
        }

        /**
         * 判断是否是父亲节点的右子节点
         *
         * @return
         */
        public boolean isRightChild() {
            return parent != null && this == parent.right;
        }

        /**
         * 返回兄弟节点
         *
         * @return
         */
        public Node<K, V> sibling() {
            if (isLeftChild()) {
                return parent.right;
            }
            if (isRightChild()) {
                return parent.left;
            }

            return null;
        }

        @Override
        public String toString() {
            String str = "";
            if (color == RED) {
                str = "【R】_";
            }
            return str + key.toString() + "," + value.toString();
        }
    }
}
